Past Event: PhD Dissertation Defense

Randomized algorithms for revealing hidden structure in data-sparse matrices

James Levitt, CSEM PhD candidate, Oden Institute, UT Austin

Abstract

This thesis describes a set of efficient algorithms for handling large dense matrices that have rank-structure.  To simplify slightly, this means that they can be tessellated into a collection of submatrices in such a way that each submatrix is either small, or of numerically low rank.  A matrix that is rank-structured can be stored economically, and is amenable to fast algorithms for performing arithmetic operations such as matrix-vector multiplication.  Rank-structured matrices arise in solvers for elliptic PDEs, for problems in data mining and statistics involving smooth kernel functions, and many more.

Recent algorithms compute approximations to rank-structured matrices by accessing the matrix only through a black-box matrix-vector multiplication routine (e.g., an FMM).  The need to operate directly on off-diagonal blocks is avoided by instead using randomized samples of the full matrix.  The first part of this thesis presents new algorithms for black-box randomized compression of rank-structured matrices.  These algorithms improve on prior work in terms of both their efficiency and their range of applicability.

In general, a matrix that admits a rank-structured approximation only does so under an appropriate ordering of its rows and columns.  Therefore, finding a suitable ordering of the rows and columns of a matrix is an essential step in building a rank-structured approximation.  In prior work, ordering techniques were developed for special classes of rank structured matrices, such as those arising from a given sparse matrix, or through a kernel matrix associated with a given set of points.  The second part of the thesis describes new techniques that apply to broader classes of rank-structured matrices and achieve a balance between computational cost, storage requirements, and accuracy.

Biography

James Levitt is a PhD candidate in the Oden Institute for Computational Engineering and Sciences, advised by Per-Gunnar Martinsson and George Biros.  His research is in numerical linear algebra, primarily focused on fast randomized algorithms for working with rank-structured matrices.  During his time as a graduate student, he completed internships at Sandia National Laboratories and at a quantitative trading firm.